|
| 1: |
|
le(0,y) |
→ true |
| 2: |
|
le(s(x),0) |
→ false |
| 3: |
|
le(s(x),s(y)) |
→ le(x,y) |
| 4: |
|
app(nil,y) |
→ y |
| 5: |
|
app(add(n,x),y) |
→ add(n,app(x,y)) |
| 6: |
|
low(n,nil) |
→ nil |
| 7: |
|
low(n,add(m,x)) |
→ if_low(le(m,n),n,add(m,x)) |
| 8: |
|
if_low(true,n,add(m,x)) |
→ add(m,low(n,x)) |
| 9: |
|
if_low(false,n,add(m,x)) |
→ low(n,x) |
| 10: |
|
high(n,nil) |
→ nil |
| 11: |
|
high(n,add(m,x)) |
→ if_high(le(m,n),n,add(m,x)) |
| 12: |
|
if_high(true,n,add(m,x)) |
→ high(n,x) |
| 13: |
|
if_high(false,n,add(m,x)) |
→ add(m,high(n,x)) |
| 14: |
|
quicksort(nil) |
→ nil |
| 15: |
|
quicksort(add(n,x)) |
→ app(quicksort(low(n,x)),add(n,quicksort(high(n,x)))) |
|
There are 15 dependency pairs:
|
| 16: |
|
LE(s(x),s(y)) |
→ LE(x,y) |
| 17: |
|
APP(add(n,x),y) |
→ APP(x,y) |
| 18: |
|
LOW(n,add(m,x)) |
→ IF_LOW(le(m,n),n,add(m,x)) |
| 19: |
|
LOW(n,add(m,x)) |
→ LE(m,n) |
| 20: |
|
IF_LOW(true,n,add(m,x)) |
→ LOW(n,x) |
| 21: |
|
IF_LOW(false,n,add(m,x)) |
→ LOW(n,x) |
| 22: |
|
HIGH(n,add(m,x)) |
→ IF_HIGH(le(m,n),n,add(m,x)) |
| 23: |
|
HIGH(n,add(m,x)) |
→ LE(m,n) |
| 24: |
|
IF_HIGH(true,n,add(m,x)) |
→ HIGH(n,x) |
| 25: |
|
IF_HIGH(false,n,add(m,x)) |
→ HIGH(n,x) |
| 26: |
|
QUICKSORT(add(n,x)) |
→ APP(quicksort(low(n,x)),add(n,quicksort(high(n,x)))) |
| 27: |
|
QUICKSORT(add(n,x)) |
→ QUICKSORT(low(n,x)) |
| 28: |
|
QUICKSORT(add(n,x)) |
→ LOW(n,x) |
| 29: |
|
QUICKSORT(add(n,x)) |
→ QUICKSORT(high(n,x)) |
| 30: |
|
QUICKSORT(add(n,x)) |
→ HIGH(n,x) |
|
The approximated dependency graph contains 5 SCCs:
{17},
{16},
{22,24,25},
{18,20,21}
and {27,29}.